import java.util.LinkedList;
import java.util.Scanner;

import static java.lang.System.exit;
import static java.lang.System.in;

/**
 * 内存类
 * @author dht925nerd@126.com
 */
public class Memory{
    /**
     * 内存大小
     */
    private int size;

    /**
     * 内存分区
     */
    public LinkedList<Zone> zones;
    /**
     * 上次分配的空闲区位置
     */
    private int pointer;

    public LinkedList<work> works=new LinkedList<work>();

    /**
     * 分区节点类
     */
    class Zone{
        /**
         * 分区大小
         */
        private int size;
        /**
         * 分区始址
         */
        private int head;
        /**
         * 空闲状态
         */
        private boolean isFree;

        private int freeaddress;

        public Zone(int head, int size) {
            this.head = head;
            this.size = size;
            this.isFree = true;
            this.freeaddress=head;
        }
    }

    class work{
        private String name;

        private int big;

        private int zoneNo;

        public work(String name,int big,int zoneNo){
            this.name=name;
            this.big=big;
            this.zoneNo=zoneNo;
        }
    }
    /**
     * 默认内存大小为 100 KB
     */
    public Memory(){
        this.size = 100;
        this.pointer = 0;
        this.zones = new LinkedList<>();
        zones.add(new Zone(0, size));
    }
    public Memory(int size,int sizeZone) {
        this.size = size;
        this.pointer = 0;
        this.zones = new LinkedList<>();
        if(size>=sizeZone) {
            zones.add(new Zone(0, sizeZone));
        }
        else{
            System.out.println("分区失败，请重试：");
            exit(0);
        }
    }

    public void addZone(int index,int more){
        zones.add(new Zone(index,more));
    }

    /**
     * 内存分配
     *  size 指定需要分配的大小
     */
    public void allocation(){
        System.out.println("1.FirstFit 2.NextFit 3.BestFit 4.WorstFit");
        System.out.print("请选择分配算法:");
        Scanner in = new Scanner(System.in);
        int algorithm = in.nextInt();
        System.out.println("请输入作业名：");
        String name=in.next();
        System.out.println("请输入作业大小：");
        int big=in.nextInt();
        switch (algorithm){
            case 1:
                fristFit(name,big);break;
            case 2:
                nextFit(name,big);break;
            case 3:
                bestFit(name,big);break;
            case 4:
                worstFit(name,big);break;
            default:
                System.out.println("请重新选择!");
        }
    }

    /**
     * 首次适应算法
     * @param size 指定需要分配的大小
     */
    private void fristFit(String name,int size){
        //遍历分区链表
        for (pointer = 0; pointer < zones.size(); pointer++){
            Zone tmp = zones.get(pointer);
            //找到可用分区（空闲且大小足够）
            if (tmp.isFree&&(tmp.size >= size)){
                works.add(new work(name,size,pointer));
                doAllocation(size, pointer, tmp);
                showZones();
                return;
            }
        }
        //遍历结束后未找到可用分区, 则内存分配失败
        System.out.println("无可用内存空间!");
    }

    /**
     * 循环首次适应算法
     * @param size 指定需要分配的大小
     */
    private void nextFit(String name,int size){
        //从上次分配空闲区位置开始遍历分区链表
        Zone tmp = zones.get(pointer);
        if (tmp.isFree && (tmp.size >= size)){
            works.add(new work(name,size,pointer));
            doAllocation(size, pointer, tmp);
            System.out.println("pointer1:"+pointer);
            showZones();
            return;
        }
        int len = zones.size();
        int i = (pointer + 1) % len;
        for (; i != pointer; i = (i+1) % len){
            tmp = zones.get(i);
            //找到可用分区（空闲且大小足够）
            if (tmp.isFree && (tmp.size >=size)){
                pointer=i;
                works.add(new work(name,size,pointer));
                doAllocation(size, i, tmp);
                System.out.println("pointer2:"+pointer);
                showZones();
                return;
            }
        }
        //遍历结束后未找到可用分区, 则内存分配失败
        System.out.println("无可用内存空间!");
    }

    /**
     * 最佳适应算法
     * @param size 指定需要分配的大小
     */
    private void bestFit(String name,int size){
        int flag = -1;
        int min = this.size;
        for (pointer = 0; pointer < zones.size(); pointer++){
            Zone tmp = zones.get(pointer);
            if (tmp.isFree && (tmp.size >= size)){
                if (min > tmp.size - size){
                    min = tmp.size - size;
                    flag = pointer;
                }
            }
        }
        if (flag == -1){
            System.out.println("无可用内存空间!");
        }else {
            pointer=flag;
            works.add(new work(name,size,pointer));
            doAllocation(size, flag, zones.get(flag));
            showZones();
            return;
        }
    }

    /**
     * 最坏适应算法
     * @param size 指定需要分配的大小
     */
    private void worstFit(String name,int size){
        int flag = -1;
        int max = 0;
        for (pointer = 0; pointer < zones.size(); pointer++){
            Zone tmp = zones.get(pointer);
            if (tmp.isFree && (tmp.size > size)){
                if (max < tmp.size - size){
                    max = tmp.size - size;
                    flag = pointer;
                }
            }
        }
        if (flag == -1){
            System.out.println("无可用内存空间!");
        }else {
            pointer=flag;
            works.add(new work(name,size,pointer));
            doAllocation(size, flag, zones.get(flag));
            showZones();
            return;
        }
    }

    /**
     * 执行分配
     * @param size 申请大小
     * @param location 当前可用分区位置
     * @param tmp 可用空闲区
     */
    private void doAllocation(int size, int location, Zone tmp) {

            zones.get(location).size=tmp.size-size;
            zones.get(location).isFree=false;
            zones.get(pointer).freeaddress=zones.get(pointer).freeaddress+size;

        System.out.println("成功分配 " + size + "KB 内存!");
    }

    /**
     * 内存回收
     * @param id 指定要回收的分区好号
     */
    public void collection(int id){
        if (id >= zones.size()){
            System.out.println("无此分区编号!");
            return;
        }
        Zone tmp = zones.get(id);
        int size = tmp.size;
        if (tmp.isFree) {
            System.out.println("指定分区未被分配, 无需回收");
            return;
        }

        zones.get(id).isFree=true;
        zones.get(id).size=zones.get(id).size+(zones.get(id).freeaddress-zones.get(id).head);
        zones.get(id).isFree = true;
        zones.get(id).freeaddress=zones.get(id).head;
        for(int i=0;i<works.size();i++){
            if(works.get(i).zoneNo==id){
               works.remove(i);
            }
        }
        System.out.println("内存回收成功!, 本次回收了 " + size + "KB 空间!");
        showZones();
    }

    /**
     * 展示内存分区状况
     */
    public void showZones(){
        System.out.println("------------------------------------");
        System.out.println("分区编号\t分区始址\t空闲始址\t分区大小\t空闲状态\t");
        System.out.println("------------------------------------");
        for (int i = 0; i < zones.size(); i++){
            Zone tmp = zones.get(i);
            System.out.println(i + "\t\t" + tmp.head + "\t\t" +tmp.freeaddress+ "\t\t"+tmp.size +"   \t" + tmp.isFree);
        }
        System.out.println("------------------------------------");
    }

    public void showWorks(){
        System.out.println("------------------------------------");
        System.out.println("此时分区中的进程为：");
        System.out.println("文件名\t文件大小\t存储位置");
        System.out.println("------------------------------------");
        for (int i=0;i<works.size();i++){
            System.out.println(works.get(i).name+"\t\t" +works.get(i).big+"\t\t" +works.get(i).zoneNo);
        }
    }
}

class Test{
    public static void main(String[] args){
        // TODO code application logic here
        System.out.println("请输入你的内存大小:");
        Scanner in = new Scanner(System.in);
        int size=in.nextInt();
        System.out.println("请输入第一个分区大小:");
        int sizeZone=in.nextInt();
        Memory memory=new Memory(size,sizeZone);

        System.out.println("请输入你想分区的数量:");
        int number=in.nextInt();

        int left=size-sizeZone;
        int index=sizeZone;

        for(int i=1;i<number;i++){
            System.out.println("请输入分区"+i+"的大小");
            int more=in.nextInt();
            if(more>left){
                System.out.println("分区失败，请重试：");
                exit(0);
            }else {
                memory.addZone(index,more);
                index+=more;
                left=size-index;
            }
        }
        if(index<size){
            memory.addZone(index,size-index);
        }
        memory.showZones();

        boolean Choose = true;
        String C;
        while (Choose == true) {
            System.out.println("您是否还要进行请求：y/n?");
            C = in.next();
            if (C.endsWith("n")) {
                Choose = false;
                memory.showWorks();
            }else if(C.endsWith("y")){
                System.out.println("请选择分配还是释放：(a/c)");
                C=in.next();
                if(C.endsWith("a")){
                    memory.allocation();
                }
                else if(C.endsWith("c")){
                    System.out.println("请选择释放分区号：");
                    memory.collection(in.nextInt());
                }
            }
        }
    }
}